package _hash

import org.junit.Assert
import org.junit.Test

/**
 *
 * https://leetcode.cn/problems/intersection-of-two-arrays/description/
 *  题型：数组-哈希法
 * ```
 * 349. 两个数组的交集
 * 给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 *
 * 示例 1：
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 *
 * 示例 2：
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 * 解释：[4,9] 也是可通过的
 *
 * 提示：
 *
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 * ```
 */
class leetcode_349 {
    @Test
    fun test_1() {
        val nums1 = intArrayOf(1, 2, 2, 1)
        val nums2 = intArrayOf(2, 2)
        val actual = intersection(nums1, nums2)
        val expected = intArrayOf(2)
        Assert.assertEquals(expected.contentToString(), actual.contentToString())
    }

    private fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
        /**
         * 题型：数组的哈希法
         *
         * 思路：
         * 找出数量少的IntArray
         * 遍历该IntArray，若存在另一个IntArray，则放入HashSet中
         * 最后，把HashSet转为IntArray
         *
         * 时间复杂度：O（N）
         *
         * 空间复杂度：O（N）
         *
         */
        val big: IntArray
        val small: IntArray
        if (nums1.size < nums2.size) {
            big = nums2
            small = nums1
        } else {
            big = nums1
            small = nums2
        }

        val hashSet: HashSet<Int> = HashSet()
        for (item in small) {
            if (big.contains(item)) {
                hashSet.add(item)
            }
        }
        return hashSet.toIntArray()
    }
}